Content-based networks are described in A Carzaniga, M. J. Rutherford, A. L. Wolf, A routing scheme for content-based networking, Department of Computer Science, University of Colorado, June 2003, the contents of which are incorporated herein by reference.
In content routed networks, a publish/subscribe data communication is provided wherein publishers can inject content into the network, and subscribers can subscribe to content from the network. The publishers and subscribers do not require knowledge of each other.
FIG. 1 depicts an example content-routed network 1, which consists of a plurality of content routers 2, 3, 4, and 5 interconnected by links 11, 12, 15 and 16; a publisher 6 (note that a content routed network typically will have a plurality of publishers but only one is shown in FIG. 1); a plurality of subscribers 7, 8, 9 and 17 (note that a content routed network can contain a large number of subscribers, i.e. millions). A publisher is a computer or user that can insert content into the network. A subscriber is a computer or user who has expressed interest in some specific content. Publisher 6 publishes a message into the content routed network by sending it over link 10 to content router 2. The term “message” is used throughout, and is intended meant to cover any type of content that can be sent to a subscriber over a network. Such content would include, for example, multimedia files.
Content router 2 matches the content of the received message against the subscriptions for the network, which the router learned of through a content routing protocol described in our copending U.S. patent application Ser. No. 11/012,113, the contents of which are incorporated herein by reference) or by some other means. Content router 2 determines that the message is required by a local subscriber on content router 2, and one or more subscribers on content router 3 and content router 4, but not by any subscribers on content router 5. As a result, a single copy of the message is sent over link 11 to content router 3, since link 11 is the preferred path to content routers 3 and 4 in this example. In addition, a copy of the message is sent over link 18 to local subscriber 17. Content router 3 delivers the message to all local subscribers which have matching subscriptions, which in this case is subscriber 7. So, a copy of the message is sent over link 13 to subscriber 7. In addition, the message is forwarded on to content router 4 over link 12. In a similar manner, content router 4 delivers the message to any local subscribers with matching subscriptions, which in this case is subscriber 8. Thus, the message is sent over link 14 to subscriber 8. Content router 4 also determines that no further content routers require a copy of the message. Full details of the content routing protocol used are disclosed in U.S. patent application Ser. No. 11/012,113 referred to above.
A content-routed network must be able to continue to provide service in the face of failures inevitable that are inevitable in complex networks. Failures can be due to hardware or software failures in the content routers 2, 3, 4, 5, or due to failures in the communications links 11, 12, 15, 16 that interconnect the content routers, as well as failures in the communications network between a content router and publishers and subscribers. Note that a communication link such as 11 may be a point-to-point physical link, or may be a logical connection such as a TCP connection over an underlying network such as an IP or MPLS network.
A content-routing protocol, such as disclosed in U.S. patent application Ser. No. 11/012,113 can re-route around failures in communication links and content routers, as long as an alternate path is available through the content-routed network. For example, if link 11 fails or content router 3 fails, content router 2 can still reach content router 4 over links 15 and 16, via content router 5. However, if a content router such as 2 fails, the attached publishers (such as 6) and subscribers (such as 17) will no longer receive service unless the content-routed network has capabilities to deal with such a failure.
For layer 2 and layer 3 networks, techniques exist for providing router redundancy for attached hosts, as disclosed in U.S. Pat. No. 5,473,599, the contents of which are incorporated herein by reference. A similar technique is described in RFC 3768, “Virtual Router Redundancy Protocol (VRRP)”, April 2004, The Internet Society, the contents of which are incorporated herein by reference. With these techniques, the concept of a virtual router is introduced, and two more physical routers are available to act on behalf of a virtual router. When a physical router is providing service on behalf of a virtual router, and the physical router fails, the protocol allows for another physical router to detect the failure and take over service for the virtual router. Attached hosts only need to address the virtual router, and so do not have to participate in the router redundancy protocol or to have any configuration changes as a result of the failure of a physical router that is providing service.
VRRP requires that the pool of routers participating in the redundancy scheme for a given virtual router share a common interface to reach the hosts which are served. Referring to FIG. 2, in IP network 29, IP routers 30 and 31 are participating in VRRP (shown by grouping 41), and are connected to a common local area network (LAN) 37. Attached to LAN 37 are hosts 33, 34, 35, and 36. On interface 38, router 30 has an address “IP A”. On interface 39, router 31 has an address “IP B”. Hosts 33 and 34 are configured to have a default gateway address of “IP A”, while hosts 35 and 36 are configured to have a default gateway address of “IP B”. Thus, when both routers 30 and 31 are functioning, any traffic sent from hosts 33 or 34 outside of the LAN 37 will be directed via router 30, while any traffic sent by hosts 35 or 36 outside of LAN 37 will be directed via router 31. However, if router 30 fails, router 31 takes over the address “IP A” on LAN 37, and issues an Address Resolution Protocol (ARP) packet to automatically refresh the binding of “IP A” in the ARP caches of any hosts on LAN 37. Thus hosts 33 and 34 will automatically send any traffic destined outside of LAN 37 via router 31. For further details, refer to the references noted above.
A key aspect of VRRP is that the routing protocols operating among routers 30, 31 and 32 in the IP network are not affected by the existence of VRRP. Since routers 30 and 31 are connected to a common LAN 37, both advertise the same IP address prefix that summarizes all reachable hosts on LAN 37. Thus, when host 36 wishes to communicate to a host on LAN 37, router 32 only needs to know that both routers 30 and 31 can reach an address on LAN 37. Router 32 can choose to reach a given host via router 30 or 31, independently of which router a host on LAN 37 is using as its current gateway. This is enabled by the common connectivity of routers 30 and 31 to LAN 37. When a router such as 30 fails, the routing protocol involved can quickly converge on the new route to reach LAN 37.
Redundancy techniques such as that offered by VRRP can also be applied to content-routed networks; however, it is not sufficient due to the complexity involved in routing based on the content of documents or messages as opposed to simply routing based on destination addresses as is done in IP networks or the like. Instead, a content-router has to advertise a very large and complex covering set to indicate a summary of the interests of all attached subscribers, as disclosed in U.S. patent application Ser. No. 11/012,113.
Referring to FIG. 3, in content-routed network 49, content routers 50 and 51 can be part of a redundancy grouping 61. Routers 50 and 51 have a connection to a common LAN 57. Router 50 connects to LAN 57 via interface 58 with an address of “IP A”. Router 51 connects to LAN 57 via interface 59 with an address of “IP B”. Subscriber 53 and subscriber 54 are provisioned to connect to a content router with an address of “IP A”, while subscribers 55, 56 and publisher 62 are provisioned to connect to a content router with an address of “IP B”. Note that with content routing, a publisher publishes documents or messages to an assigned content router, and is not concerned with which subscribers in the network will receive published documents or messages. Similarly, subscribers indicate to their assigned content router what their interests are (through content-based subscriptions), and do not have to know where in the network the content is being originated from. Subscribers and publishers typically connect to a content router using a protocol such as TCP, although many such protocols can be utilized.
As disclosed in U.S. patent application Ser. No. 11/012,113, the content-routing protocol in network 49 distributes covering sets of subscriptions among the content routers, enabling a content router to know where it needs to route a given message based on the interests of subscribers in the network. Thus, router 50 can compute and publish a covering set which summarizes the subscriptions of all its connected subscribers, and router 51 and router 52 can do the same. If router 50 fails, techniques such as those offered with VRRP can be utilized to allow router 51 to take over the address “IP A”, and ARP can be used to re-bind “IP A” to interface 59 of router 51. Any active TCP connections to “IP A” will fail, and when the TCP connections are re-established, they will now be made to router 51 instead of router 50. Thus, the techniques of VRRP can hide the details of router redundancy from attached subscribers and publishers on LAN 57. It should be noted, however, that a change in behavior is needed from the standard VRRP behavior. VRRP specifies that when a router takes over an IP address from another router, it cannot terminate any traffic addressed to that IP address. However, in content-routed networks, when a content-router takes over an interface IP address from another content-router, it must terminate traffic sent to that IP address since subscribers and publishers are actually communicating directly with the content-router, as opposed to using it just as a gateway as in the case of IP routing.
Looking at router 52, it sees a different covering set from content router 50 and from content router 51, since content router 50 is advertising a summary of the subscriptions from subscribers 53 and 54, while content router 51 is advertising a summary of the subscriptions from subscribers 55 and 56. Note that in reality there can be tens of thousands of subscribers off of a single content router. Thus, unlike in the scenario of an IP network described above, with content-routing the use of VRRP alone does not solve the redundancy problem. When content router 50 fails, content router 52 must learn that content router 51 now requires a different set of documents or messages to be routed to it that now satisfies the needs of subscribes 53, 54, 55 and 56, instead of just 55 and 56.
One possible inventive solution to the above problem not forming part of the state of the art, but considered by the inventors, would be for content router 50 and content router 51 to always advertise a covering set which encompasses the subscriptions of subscribers 53, 54, 55 and 56. However, this technique would be inefficient, since when publisher 36 publishes a message to content router 52 which matches that covering set, content router 52 must send a copy of message over link 62 to content router 50, and send a copy of the message over link 63 to content router 51. However, content router 50 may or may not actually require the message based on the interests of the subscribers 53 and 54, and content router 51 may or may not need the message based on the interests of subscribers 55 and 56. This technique therefore wastes bandwidth on links 62 and 63, and wastes message processing resources on content routers 52 (since it may send more message than necessary) and content routers 50 and 51 (since they receive more messages than necessary). Moreover, as a subscriber such as 53 adds or removes subscriptions, this can cause both content routers 50 and 51 to have to communicate with other content routers to update their covering set and thus result in more control plane resource consumption (memory and processing).
Another possible inventive solution to the above problem not forming part of the state of the art, but considered by the inventors, would be for a content router such as 51 to dynamically re-compute and re-advertise its covering set as it takes over or releases control of a virtual router. For example, when content router 50 fails, content router 51 can advertise a new covering set that now encompasses the subscriptions of subscribers 53, 54, 55 and 56. When content router 50 recovers and provides services again to subscribers 53 and 54, content router 51 can re-advertise a covering set that now only reflects the needs of subscribers 55 and 56. However, the computations involved in such covering set changes, and the resulting content-routing protocol traffic and processing required at each content router in the network is very significant. Thus, while this technique solves the problem of wasting bandwidth as described above, it leads to slow convergence time after a router failure.
While the above description refers to content-routed networks, the same sort of problems exist with any type of routing where there is a significant amount of routing information to be advertised and the information to be advertised is affected by the activity state of the router.
What is desirable is a redundancy scheme for data communication networks that provides a very fast and efficient scheme for reacting to failures.